package com.boot.leetcode;

import java.util.*;

/**
 * @Package com.boot.leetcode
 */
public class LinkNode {
    private int val;
    private LinkNode next;

    public LinkNode(int val) {
        this.val = val;
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public LinkNode getNext() {
        return next;
    }

    public void setNext(LinkNode next) {
        this.next = next;
    }


    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        LinkNode node = (LinkNode) o;
        return val == node.val &&
                next == node.next;
    }

    @Override
    public int hashCode() {
        return this.val;
    }

    @Override
    public String toString() {
        return "LinkNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }

    public static LinkNode ReverseList(LinkNode head) {
        Stack<LinkNode> stack =new Stack<>();
        while (head !=null){
            stack.push(head);
            head=head.next;
        }
        if(stack.isEmpty()){
            return null;
        }

        LinkNode node=stack.pop();
        LinkNode newlink=node;
        while (!stack.isEmpty()){
            LinkNode n=stack.pop();
            node.next=n;
            node=node.next;
        }
        node.next=null;

        return newlink;
    }

    public static LinkNode ReverseList1(LinkNode head) {
        //新链表
        LinkNode newHead = null;
        while (head !=null){
            LinkNode tmp = head.next;
            head.next = newHead;
            newHead = head;
            head = tmp;
        }
        //while (head != null) {
        //    //先保存访问的节点的下一个节点，保存起来
        //    //留着下一步访问的
        //    LinkNode temp = head.next;
        //    //每次访问的原链表节点都会成为新链表的头结点，
        //    //其实就是把新链表挂到访问的原链表节点的
        //    //后面就行了
        //    head.next = newHead;
        //    //更新新链表
        //    newHead = head;
        //    //重新赋值，继续访问
        //    head = temp;
        //}
        //返回新链表
        return newHead;
    }

    /**
     * 查找链表环
     */
    public static LinkNode findCyclNode(LinkNode head){
        Set<LinkNode> nodeSet =new HashSet<>();
        LinkNode cyclNode=null;
        while ( head !=null ){
            if(nodeSet.contains(head)){
                cyclNode=head;
                return head;
            }
            nodeSet.add(head);
            head=head.next;
        }
        return cyclNode;
    }

    public static LinkNode findCyclNode1(LinkNode head){
        if(head==null || head.next ==null ){
            return null;
        }

        LinkNode fast=head,slow=head;
        while (fast !=null){

            slow =slow.next;
            fast = fast.next.next;

            if(fast.equals(slow)){
                LinkNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }

        }

        return null;
    }

    public static LinkNode sortLink(LinkNode head){
        if(head == null){
            return null;
        }

        List<LinkNode> nodes=new ArrayList<>();
        while (head !=null){
            LinkNode next=head.next;
            head.next=null;
            nodes.add(head);
            head=next;
        }

        nodes.sort(Comparator.comparing(e->e.val));
        LinkNode newLink=nodes.get(0);
        LinkNode tmp=nodes.get(0);
        for (int i = 1; i < nodes.size(); i++) {
            LinkNode node=nodes.get(i);
            tmp.next=node;
            tmp=node;
        }
        return newLink;
    }

    public static LinkNode sortLink2(LinkNode head){
        if(head == null){
            return null;
        }

        int len=0;
        LinkNode root=head;
        while (root !=null){
            LinkNode next=root.next;
            root=next;
            len++;
        }
        root=head;

        LinkNode[] arr=new LinkNode[len];
        int pos=0;
        while (root !=null){
            LinkNode next=root.next;
            root.next=null;
            arr[pos]=root;

            for (int j=pos;j>0;j--){//排序数组
                if(arr[j].val<arr[j-1].val){
                    LinkNode tmp=arr[j-1];
                    arr[j-1]=arr[j];
                    arr[j]=tmp;
                }
            }

            pos++;
            root=next;
        }

        LinkNode newLink=arr[0];
        LinkNode tmp=arr[0];
        for (int i = 1; i < arr.length; i++) {
            LinkNode node=arr[i];
            tmp.next=node;
            tmp=node;
        }
        return newLink;
    }
    public static LinkNode sortLink3(LinkNode head){
        PriorityQueue<LinkNode> heap = new PriorityQueue<LinkNode>((a,b)->a.val-b.val);
        while(head!=null)
        {
            LinkNode next=head.next;
            heap.offer(head);
            head.next=null;
            head=next;
        }

        LinkNode dummy=heap.poll();
        LinkNode cur = dummy;
        while(heap.size()>0)
        {
            cur.next=heap.poll();
            cur=cur.next;
        }
        cur.next=null;
        return dummy;
    }

    /**
     * 回文链表 从前往后 和从后往前 是一样的
     *  1 2 3 3 2 1
     *
     */
    public static boolean isPalindrome(LinkNode head) {
        boolean res =true;
        Stack<LinkNode> stack=new Stack();
        LinkNode root=head;
        while (root !=null){
            stack.push(root);
            root = root.next;
        }

        while (head !=null){
            if(head.val != stack.pop().val){
                return false;
            }
            head =head.next;
        }
        return  res;
    }

    public static boolean isPalindrome1(LinkNode head) {
        boolean res =true;
        if(head == null){
            return false;
        }

        List<LinkNode> nodes=new ArrayList<>();
        LinkNode root=head;
        while (root !=null){
            nodes.add(root);
            root = root.next;
        }

        int left=0,right=nodes.size()-1;
        while (left<right){
            if(nodes.get(left).val != nodes.get(right).val){
                return false;
            }
            left++;
            right--;
        }

        return  res;
    }

    public static LinkNode delNode(LinkNode head,int val) {
        Stack<LinkNode> nodes=new Stack<>();
        while (head !=null){
            LinkNode next =head.next;
            if(head.val != val){
                nodes.add(head);
                head.next=null;
            }
            head=next;
        }

        LinkNode newLink=nodes.pop();
        LinkNode cur=newLink;
        while (!nodes.isEmpty()){
            LinkNode n=nodes.pop();
            cur.next=n;
            cur=n;
        }

        return newLink;
    }

    public static LinkNode delNode1(LinkNode head, int val) {

        if(head.val == val){
            return head.next;
        }

        LinkNode pre=head,cur=head.next;
        while (cur !=null && cur.val != val){
            pre=cur;
            cur=cur.next;
        }

        if(cur !=null){
            pre.next=cur.next;
        }

        return head;
    }

    public static void main(String[] args) {
        LinkNode n1=new LinkNode(1);
        LinkNode n2=new LinkNode(2);
        LinkNode n3=new LinkNode(3);
        LinkNode n4=new LinkNode(4);
        LinkNode n5=new LinkNode(5);
        n1.next=n2;
        n2.next=n4;
        n3.next=n5;
        n4.next=n3;

        LinkNode newlink = ReverseList1(n1);
        System.out.println(newlink);
        System.out.println(sortLink3(newlink));

        //n1 = ReverseList1(newlink);
        //
        //LinkNode n6=new LinkNode(6);
        //n5.next=n6;
        //n6.next =n4;
        //System.out.println(findCyclNode(n1));
        //System.out.println(findCyclNode1(n1));

        LinkNode s1=new LinkNode(1);
        LinkNode s2=new LinkNode(2);
        LinkNode s3=new LinkNode(3);
        LinkNode s4=new LinkNode(4);
        LinkNode s5=new LinkNode(3);
        LinkNode s6=new LinkNode(2);
        LinkNode s7=new LinkNode(1);

        s1.next=s2;
        s2.next=s3;
        s3.next=s4;
        s4.next=s5;
        s5.next=s6;
        s6.next=s7;

        System.out.println(isPalindrome(s1));
        System.out.println(isPalindrome1(s1));
        System.out.println(s1=delNode(s1,4));
        System.out.println(delNode1(s1,3));

    }
}
